from LeetCoder import *


class Solution:

    def maxMoves(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])

        @cache
        def f(x, y, v):
            if x < 0 or x == m or y < 0 or y == n or grid[x][y] <= v:
                return 0
            a1 = f(x - 1, y + 1, grid[x][y])
            a2 = f(x, y + 1, grid[x][y])
            a3 = f(x + 1, y + 1, grid[x][y])
            # print(x, y, max(a1, a2, a3) + 1)
            return max(a1, a2, a3) + 1

        ans = 0
        for i in range(m):
            ans = max(ans, f(i, 0, -1))
        return ans - 1


s = Solution()
print(s.maxMoves(grid=[[3, 2, 4], [2, 1, 9], [1, 1, 7]]))
print(
    s.maxMoves(
        grid=[[2, 4, 3, 5], [5, 4, 9, 3], [3, 4, 2, 11], [10, 9, 13, 15]]))
